package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         207,
		Discription: "课程表",
		Level:       2,
		Labels: map[string]int{
			"拓扑排序": 1,
			"哈希表":  1,
		},
	})
}

func CanFinish(numCourses int, prerequisites [][]int) bool {
	//图（只包括带后序节点）：节点的后序节点有哪些
	graph := make(map[int][]int, 0)
	//每个节点的入度，必须是[]int
	inDegree := make([]int, numCourses)
	for _, pre := range prerequisites {
		inDegree[pre[0]]++
		graph[pre[1]] = append(graph[pre[1]], pre[0])
	}

	//用队列遍历，遍历到一个节点，就把该节点的每个后序节点的入度-1，若入度为0则将后序节点进队
	q := make([]int, 0)
	for course, ins := range inDegree {
		if ins == 0 {
			q = append(q, course)
		}
	}

	count := 0
	for len(q) != 0 {
		course := q[0]
		q = q[1:]
		count++
		for _, postCourse := range graph[course] {
			inDegree[postCourse]--
			if inDegree[postCourse] == 0 {
				q = append(q, postCourse)
			}
		}
	}

	return count == numCourses
}
